package com.sheng.leetcode.year2022.month03.day25;

import org.junit.Test;

import java.math.BigDecimal;

/**
 * @author liusheng
 * @date 2022/03/25
 * 172. 阶乘后的零
 *
 * 给定一个整数 n ，返回 n! 结果中尾随零的数量。
 * 提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1 
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：0
 * 解释：3! = 6 ，不含尾随 0
 * 示例 2：
 *
 * 输入：n = 5
 * 输出：1
 * 解释：5! = 120 ，有一个尾随 0
 * 示例 3：
 *
 * 输入：n = 0
 * 输出：0
 *
 * 提示：
 *
 * 0 <= n <= 104
 *  
 *
 * 进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0172 {

    @Test
    public void test01(){
        int n = 30;
        System.out.println(new Solution().trailingZeroes(n));
    }
}
class Solution {
    public int trailingZeroes(int n) {
        BigDecimal bigDecimal = new BigDecimal("1");
        while (n > 0) {
            bigDecimal = bigDecimal.multiply(new BigDecimal(n));
            n--;
        }
        int bn2 = 0;
        int bn5 = 0;
        System.out.println(bigDecimal);
        BigDecimal[] bigDecimals = bigDecimal.divideAndRemainder(new BigDecimal(2));
        while (bigDecimal.divideAndRemainder(new BigDecimal(2))[1].compareTo(BigDecimal.ZERO) == 0) {
            bn2++;
            bigDecimal = bigDecimal.divideAndRemainder(new BigDecimal(2))[0];
        }
        while (bigDecimal.divideAndRemainder(new BigDecimal(5))[1].compareTo(BigDecimal.ZERO) == 0) {
            bn5++;
            bigDecimal = bigDecimal.divideAndRemainder(new BigDecimal(5))[0];
        }
        return bn2 > bn5 ? bn5 : bn2;
    }
}
/**
 * 4岁的阿尔和6岁的爱德华是两兄弟，从小就对炼金术很有兴趣。
 * 一天，阿尔看到哥哥在算乘法，阿尔看了觉得很新奇，
 * 怎么哥哥计算出来的结果后面那么多圈圈，原来这是他们温柔的妈妈安排爱德华做的一道数学题，
 * 要他计算从a到b所有整数的乘积。妈妈看到阿尔看得那么入神，
 * 也想考验一下阿尔，对阿尔说：“你能数出哥哥计算的结果末尾的0有多少个吗？”，
 * 聪明的阿尔把计算结果看了1秒很快就把正确答案告诉妈妈，
 * 你也能和阿尔一样聪明吗？输入两个正整数a和b，求a到b之间（包含a、b）所有整数的积末尾有多少个0。
 */
